import java.util.LinkedList;
import java.util.Queue;

class Node{
    public int val;
    public Node left;
    public Node right;
    public Node(int val){
        this.val=val;
    }
}

public class BinaryTree{

    int size(Node root){
        if(root==null){
            return 0;
        }
        return size(root.left)+size(root.right)+1;
    }

    int getLeafNodeCount(Node root){
        if(root==null){
            return 0;
        }
        if(root.left==null&&root.right==null){
            return 1;
        }
        return getLeafNodeCount(root.left)+getLeafNodeCount(root.right);
    }

    int getKLevelNodeCount(Node root,int k){
        if(root==null||k<=0){
            return 0;
        }
        if(k==1){
            return 1;
        }
        return getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right,k-1);
    }

    int getHeight(Node root){
        if(root==null){
            return 0;
        }
        int leftHeight=getHeight(root.left);
        int rightHeight=getHeight(root.right);
        return leftHeight>rightHeight?leftHeight+1:rightHeight+1;
    }

    Node find(Node root,char val){
        if(root==null){
            return null;
        }
        if(root.val==val){
            return root;
        }
        Node ret=find(root.left,val);
        if(ret!=null){
            return ret;
        }
        ret=find(root.right,val);
        if(ret!=null){
            return ret;
        }
        return null;
    }

    boolean isCompleteTree(Node root){
        if(root==null){
            return true;
        }
        Queue<Node> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            Node cur=queue.poll();
            if(cur!=null){
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else{
                break;
            }
        }
        while(!queue.isEmpty()){
            Node top=queue.peek();
            if(top!=null){
                return false;
            }
            queue.poll();
        }
        return true;
    }

}